// 105. 从前序与中序遍历序列构造二叉树
package LeetcodeHot100;

import java.util.Arrays;



public class Solution105 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0)
            return null;
        TreeNode root = new TreeNode(preorder[0]);
        if (preorder.length == 1) {
            root.left = null;
            root.right = null;
            return root;
        }

        int numLeft = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == preorder[0]) {
                numLeft = i;
                break;
            }
        }
        root.left = buildTree(Arrays.copyOfRange(preorder, 1, numLeft + 1), Arrays.copyOfRange(inorder, 0, numLeft));
        root.right = buildTree(Arrays.copyOfRange(preorder, numLeft + 1, preorder.length),
                Arrays.copyOfRange(inorder, numLeft + 1, inorder.length));
        return root;
    }
}
